package com.wzp.algorithm.must;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int index = arr[low];
        int i = low;
        int j = high;
        while (i < j) {
            while (arr[j] >= index && i < j) {
                j--;
            }
            while (arr[i] <= index && i < j) {
                i++;
            }
            if (i < j) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
        // 这里的arr[i]一定是停小于index的,经过i、j交换后i处的值一定是小于index的(j先走)
        arr[low] = arr[i];
        arr[i] = index;
        System.out.println(Arrays.toString(arr));
        // 对左边快排
        quickSort(arr, low, j - 1);
        // 对右边快排
        quickSort(arr, j + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = {3, 0, 4, 1, 5, 2, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}